package labnumero4;

//importo para trabajar con Arraylist
import java.util.ArrayList;




/**
 *ALGORITMOS Y ESTRUCTURA DE DATOS
 *HOJA DE TRABAJO 3
 * SECCION 10
 * 
 * ROGER DIAZ  12176
 * Victor Fuentes 12298
 * Mayra Beb 12537
 * Marcos Lopez 12529
 * 
 */

public class MergeSort {
        //variables
    ArrayList<String> lista;//arraay de entrada desde main
    ArrayList<String> listaOrdenada;//array ya ordenada, usada para imprmir
    int largo;//largo de list, list usada para trabajo de metodos
    int list[];//lista para el manejo de los lementos
    int list2[];//lista ya ordenada usada para volver a ejectuar el algoritmos para comprobar tiempo
    
    //Constructor
        public MergeSort(ArrayList h){
        listaOrdenada=new ArrayList<>();
        lista=h;
        largo=lista.size()-1;
        list=new int[largo+1];
        for(int a=0; a<=largo;a++){
            int id=0;
            id=Integer.parseInt(lista.get(a));
            list[a]=id;
        }
        //luego de crear el objeto, de una vez trabaja los metodos propios de MergeSort
        mergeSort(list,list.length);//metodo para ordenar        
    }
    
  //Bailey, D. 2007. Java Structures, Cap 9: List. Williams Collage. Estados Unidos de America. Pp 127
        //con la division de la lista trabaja para ordenar
    private static void merge(int data[], int temp[], int low, int middle, int high){
    int ri = low;
    int ti= low;
    int di = middle;
    while(ti < middle && di <= high){
    if (data[di] < temp[ti]){
    data[ri++]=data[di++];
    }
    
    else{
        data [ri++]=temp[ti++];
        
    }
    }
    while(ti< middle){
    data[ri++]=temp[ti++];
    
    }
    }
    
    //esto sirve para volver a realizar el proceso
        public void EXE2(){
        mergeSort(list2,list.length);//en este punto list ya esta ordenada, volver a ejecutar algoritmo para comprobar tiempo
    }
    
     //Bailey, D. 2007. Java Structures, Cap 9: List. Williams Collage. Estados Unidos de America. Pp 128     
        //este metodo va a hacer que vayan los datos de menor a mayor
    private static void mergeSortRecursive(int data[], int temp[], int low, int high){
    int n=high-low+1;
    int middle= low + n/2;
    int i;
    if(n<2) return;
    for (i=low; i<middle; i++){
    temp[i]=data[i];
    }
    mergeSortRecursive(temp, data, low, middle-1);
    mergeSortRecursive(data, temp, middle, high);
    merge(data, temp, low, middle, high);
    }
    
      //Bailey, D. 2007. Java Structures, Cap 9: List. Williams Collage. Estados Unidos de America. Pp 130
    //este metodo se usa en el constructor y utiliza todos los demas que son propios de mergesort
    //ya que mergesortRecursive llama a merge
    public static void mergeSort(int data[], int n){
    mergeSortRecursive(data, new int [n], 0, n-1);
    }
    
    //GETTER
        public int getLargo(){
        return largo;
    }
    
      //GETTER  
    public int getLargoList(){
        return list.length;
    }
            
    
    
    //PARA IMPRESION
    public void imprimirArrayDesordenado(){
        System.out.println(lista);  
    }
    
     //PARA IMPRESION
    public String imprimirListOrdenado(){
        String salida="";
        for(int i=0; i<=largo;i++){
            salida+=list[i];
        }
        return salida;       
    }
    
        //metodo para copiar list a list2, list2 estara ya ordenada y entrada a exe2 para repetir algoritmo de orden
    public void copiarLista(){
        list2=new int[list.length];
        for(int i=0;i<list.length;i++){
            list2[i]=list[i];
        }
    }
    
     //PARA IMPRESION
        public String imprimirList2Ordenada(){
        int i=list2.length;
        String re="";
        for(int a=0;a<i;a++){
            re+=" "+list2[a]+",";
        }
        
        
        return re;
    }
    
    //Este metodo sirve para agregar la lista a un Arraylist
    public void Ordenada(){
        int i=list.length;
        String add="";
        for(int a=0;a<i;a++){
          
            add=Integer.toString(list[a]);
            listaOrdenada.add(add);
        }
    }
    
     //PARA IMPRESION
    public void imprimirArrayOrdenado(){
        System.out.println(listaOrdenada);
        System.out.println(listaOrdenada.size());
    }

    
}
    
    

